package codeRandomThoughts.Test416分割等和子集;

import java.util.Arrays;

public class Solution {
    public boolean canPartition(int[] nums) {
        //可以直接转化为01背包问题
        //nums数组既是value又是weight
        //背包容量size = sum/2
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;

        //背包容量
        int size = sum / 2;

        //weight[]
        int[] weight = nums;

        //value[]
        int[] value = nums;

        //dp[j]代表从下标0~i的物品里面任意选取,能获得的最大价值是多少
        int[] dp = new int[size + 1];

        //初始化 也就是i=0时
        for (int j = weight[0]; j <= size; j++) {
            dp[j] = value[0];
        }

        for (int i = 1; i < weight.length; i++) {
            for (int j = size; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                //如果在过程中已经能塞满整个背包
                if (dp[j] == size) {
                    return true;
                }
            }
        }

        return false;
    }
}
